As computer programming becomes more sophisticated ever greater performance demands are placed upon basic logic combinational networks such as adders, multipliers, and the like. In general, these demands have been met by utilizing state-of-the-art transistor processing techniques to reduce switching delays. However, as the number of bits to be logically synthesized increases, this solution becomes inadequate. Accordingly, renewed emphasis is being placed on the design of these basic logic networks.
Hardware multiplication is generally used in digital signal and data processing systems to perform high speed binary multiplication. Multiplication of binary numbers is conducted in essentially the same way as decimal number multiplication. For every bit in one of the factors (the multiplier) a multiple is formed of the other factor (the multiplicand) and is added to a running total. Successive partial products are shifted one position to the left with the final product being obtained from the sum of the partial products. If the whole operation is to be conducted simultaneously by a fast multiplier, then one adder is needed for every digit in the multiplier.
A large number of combinational logic multipliers now exist which are capable of high speed multiplication. Most, if not all, of these multiplication circuits employ carry save adders (or a variation thereof) connected branchwise to add (to the extent possible) partial products in parallel. By way of example, consider a conventional carry save multiplier, Dadda multiplier, Wallace tree multiplier or binary tree multiplier, all of which are well known in the open literature and all of which employ carry save adders connected in multiple stages and coupled to receive partial products and output based thereon a binary number comprising the desired product of the input factors (see, e.g., Habibi and Wintz, "Fast Multiplier," IEEE Transaction on Computers, pp. 154-157 (February 1970)).
Perhaps the most widely used hardware multiplier approach today is the Wallace tree multiplier. This multiplier requires complex interconnections of carry save adders to enhance performance summation within each column of the array multiplier. Although successful in enhancing performance, the Wallace tree multiplier is difficult to implement, often requiring wiring by hand (which is obviously time consuming and inflexible), and results in a very irregular structure that is hard to diagnose. Further, to optimize performance, interconnections must be carefully planned in order to minimize stray capacitance.
Thus, a need exists in the computer system art for a novel combinatorial logic approach comprising a less complex, high speed binary multiplier. The present invention addresses this need by employing a plurality of regular carry select adders or carry look-ahead adders in a novel binary multiplication array structure having a hierarchical tree configuration.